| class WTD_DIGRAPH{NTP<$STR,WTP<$NUMBER{WTP}} < $LBLD_DIGRAPH{NTP,WTP,WTP} |
|---|
| **** | A standard directed graph with node and edge weights of type WTP. The nodes of the graph are of type NTP. |
| $LBLD_DIGRAPH{_,_,_} | $DIGRAPH{_} | $RO_DIGRAPH{_} | $GRAPH{_,_} | $STR | $ELT{_} | $ELT | LBLD_DIGRAPH{_,_,_} | LBLD_DIGRAPH_INCL{_,_,_} | DIGRAPH{_} | $SUPPORTS_REHASH | DIGRAPH_INCL{_} | RO_DIGRAPH_INCL{_} | COMPARE{_} |
| add_node(n: NTP) .. Included as add_node |
|---|
| **** | Short hand for "add_node(n:NTP): NTP" that is only valid for this sort of graph, where the user specifies the node type. |
| add_node(n: NTP): NTP .. Included as add_node |
|---|
| **** | Add the node "n". In this kind of hash digraph, the node index returned is guaranteed to be the same as the node "n". Note that this is not generally true for graphs |
| add_node(n: NTP,w: NLB) .. Included as add_node |
|---|
| **** | Add the node "n" to the graph with the node label "w" |
| add_node(n: NTP,l: NLB): SAME .. Included as add_node |
|---|
| **** | Version of "add_node" that returns self for convenience in chaining operations |
| add_node: NTP .. Included as add_node |
|---|
| **** | Add a new node and return the index |
| add_node_labelled(w: NLB): NTP .. Included as add_node_labelled |
|---|
| **** | Add the node "n" to the graph with the node label "w" |
| are_all_edges_labelled: BOOL .. Included as are_all_edges_labelled |
|---|
| **** | Return true if all the edges in self are labelled |
| are_all_nodes_labelled: BOOL .. Included as are_all_nodes_labelled |
|---|
| **** | Return true if all the nodes in self have a label |
| bellman_ford(s:NTP, out d:MAP{NTP,WTP}, out |
|---|
| **** | Call into the digraph algorithm class |
| connect(e: DIEDGE{NTP}) .. Included as connect |
|---|
| **** | Connect source to target. No change if the edge already exists Add the nodes if they do not exist |
| connect(f,s: NTP) .. Included as connect |
|---|
| connect(f,s: NTP): SAME .. Included as connect |
|---|
| connect(n1,n2: NTP,w: ELB) .. Included as connect |
|---|
| **** | Add an edge from "n1" to "n2" with the edge label "w" |
| connect(s,d: NTP,l:ELB): SAME .. Included as connect |
|---|
| **** | Version of "connect" that returns self for convenience in chaining connections |
| copy: $DIGRAPH{NTP} .. Included as copy |
|---|
| create: SAME .. Included as create |
|---|
| delete_node(n: NTP) .. Included as delete_node |
|---|
| **** | Delete a node from the graph, and all its accompanying edges |
| dijkstra(src:NTP,out dist:MAP{NTP,WTP},out |
|---|
| **** | Call into the digraph algorithm class |
| disconnect(e: DIEDGE{NTP}) .. Included as disconnect |
|---|
| **** | Deletes the edge "e". |
| disconnect(f,s: NTP) .. Included as disconnect |
|---|
| edge_label(e:DIEDGE{NTP}): ELB .. Included as edge_label |
|---|
| **** | Return the edge label if it exists, void otherwise |
| equals(g: $RO_DIGRAPH{NTP}):BOOL .. Included as equals |
|---|
| **** | True if both have the same set of nodes and edges |
| has(n: NTP): BOOL .. Included as has |
|---|
| has_edge(e: DIEDGE{NTP}): BOOL .. Included as has_edge |
|---|
| has_edge_label(e:DIEDGE{NTP}): BOOL .. Included as has_edge_label |
|---|
| has_node(n: NTP): BOOL .. Included as has_node |
|---|
| has_node_label(n:NTP): BOOL .. Included as has_node_label |
|---|
| is_empty: BOOL .. Included as is_empty |
|---|
| is_identical(g: SAME): BOOL .. Included as is_identical |
|---|
| **** | Check whether the two graphs have the same nodes, edges in the same order |
| is_topo_order(n: $ARR{NTP}):BOOL .. Included as is_topo_order |
|---|
| **** | Return true if the nodes in "n" do not violate the precedence relations expressed by the graph "self" |
| str: STR .. Included as n |
|---|
| **** | Print out the graph using the bound routine "f" for the nodes |
| n_adjacent(n:NTP): INT .. Included as n_adjacent |
|---|
| n_edges: INT .. Included as n_edges |
|---|
| **** | Returns the number of edges in the graph, making sure each edge is only counted once |
| n_incoming(n: NTP): INT .. Included as n_incoming |
|---|
| **** | Number of incoming edges from node "n" |
| n_neighbors(n: NTP): INT .. Included as n_neighbors |
|---|
| **** | Returns the number of neighbors of "n" (nodes are only counted once) |
| n_nodes: INT .. Included as n_nodes |
|---|
| n_outgoing(n: NTP): INT .. Included as n_outgoing |
|---|
| **** | Number of outgoing edges from node "n" |
| elt_eq(e1,e2:ETP):BOOL .. Included as node_equal |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| node_label(n:NTP): NLB .. Included as node_label |
|---|
| **** | Return void if the node is not labelled |
| rehash .. Included as rehash |
|---|
| set_edge_label(e: DIEDGE{NTP},w: ELB) .. Included as set_edge_label |
|---|
| **** | Set the label of edge "e" to "w" |
| set_node_label(n: NTP,w: NLB) .. Included as set_node_label |
|---|
| **** | Set the label of node "n" to "w" |
| size: INT .. Included as size |
|---|
| str: STR .. Included as str |
|---|
| **** | Print out the graph using the bound routine "f" for the nodes |
| adjacent!(once n: NTP): NTP .. Included as adjacent! |
|---|
| **** | Adjacent is aliased to "outgoing" |
| bf!(once n: NTP): NTP .. Included as bf! |
|---|
| **** | Yield all nodes in breadth first order |
| df!(once n: NTP): NTP .. Included as df! |
|---|
| **** | Yield all nodes in depth first order |
| edge!(out label: ELB): DIEDGE{NTP} .. Included as edge! |
|---|
| **** | Yield successive edges and set the corresponding value of "label" to be the edge's label, or void otherwise |
| edge!: DIEDGE{NTP} .. Included as edge! |
|---|
| **** | Return all edges in the graph |
| elt!: NTP .. Included as elt! |
|---|
| **** | Returns the nodes of the graph |
| incoming!(once n: NTP): NTP .. Included as incoming! |
|---|
| incoming!(once n: NTP, out a_node_label: NLB, out a_edge_label: ELB): NTP .. Included as incoming! |
|---|
| **** | Yield successive incoming nodes to node "n". Set the out parameter "a_node_label" to be the corresponding label of the incoming node and "a_edge_label" to be the label of the corresponding edge from the incoming node to "n" |
| layer!: SET{NTP} .. Included as layer! |
|---|
| **** | Peel off successive layers from the graph, starting with the root set. Stop when no more roots (nodes with no incoming edges) can be found. |
| max_weight_path_node!(once src,once sink: NTP): NTP |
|---|
| **** | Please see the comment at WTD_DIGRAPH_ALG{_,_,_,_}::max_weight_path |
| node!(out label: NLB): NTP .. Included as node! |
|---|
| **** | Yield successive nodes and set the corresponding value of "label" to the node's label (or void, if it is not labelled) |
| node!: NTP .. Included as node! |
|---|
| outgoing!(once n: NTP): NTP .. Included as outgoing! |
|---|
| outgoing!(once n: NTP, out a_node_label: NLB, out a_edge_label: ELB): NTP .. Included as outgoing! |
|---|
| **** | See incoming! |
| sink!: NTP .. Included as sink! |
|---|
| **** | Yield all the sink nodes (with n_outgoing = 0) in self |
| source!: NTP .. Included as source! |
|---|
| **** | Yield all the source nodes with n_incoming = 0 in self |
| topo_order!: NTP .. Included as topo_order! |
|---|
| **** | Yield the nodes of self in some topologically sorted orer |
| check_node(n: NTP,routine_name: STR): BOOL .. Included as check_node |
|---|
| attr edge_labels: MAP{DIEDGE{NTP},ELB}; .. Included as edge_labels |
|---|
| attr edge_labels: MAP{DIEDGE{NTP},ELB}; .. Included as edge_labels |
|---|
| elt_hash(e:ETP):INT .. Included as elt_hash |
|---|
| **** | A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants. |
| elt_lt(e1,e2:ETP):BOOL .. Included as elt_lt |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_nil: ETP .. Included as elt_nil |
|---|
| **** | Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void
_ |
| attr incoming_map: FMULTIMAP{NTP,NTP}; .. Included as incoming_map |
|---|
| attr incoming_map: FMULTIMAP{NTP,NTP}; .. Included as incoming_map |
|---|
| init_labels .. Included as init_labels |
|---|
| **** | This routine initializes the label datastructures. Since this class is meant to be used by inclusion, this routine should be called after the class has been created |
| is_elt_nil(e:ETP):BOOL .. Included as is_elt_nil |
|---|
| attr node_generator: $SUCC_STREAM{NTP}; .. Included as node_generator |
|---|
| **** | Generator of nodes which is used by add_node. If a node generator is not provided at creation time, then add_node cannot be used, since the graph does not know how to create new unique nodes. |
| attr node_generator: $SUCC_STREAM{NTP}; .. Included as node_generator |
|---|
| **** | Generator of nodes which is used by add_node. If a node generator is not provided at creation time, then add_node cannot be used, since the graph does not know how to create new unique nodes. |
| attr node_labels: MAP{NTP,NLB}; .. Included as node_labels |
|---|
| attr node_labels: MAP{NTP,NLB}; .. Included as node_labels |
|---|
| attr node_list: FLIST{NTP}; .. Included as node_list |
|---|
| **** | List of nodes in the graph |
| attr node_list: FLIST{NTP}; .. Included as node_list |
|---|
| **** | List of nodes in the graph |
| node_str(n: NTP): STR .. Included as node_str |
|---|
| **** | There should not be void nodes in the graph! |
| ob_str(n: $OB): STR .. Included as ob_str |
|---|
| create(node_gen: $SUCC_STREAM{NTP}): SAME .. Included as old_create |
|---|
| **** | Create a new digraph. Store "node_gen" as a generator of nodes, so that when "add_node: NTP" is called it can generate unique new nodes. |
| create: SAME .. Included as old_create |
|---|
| **** | Create a new digraph and return it. Since a node generator is not specified, it will not be possible to call the "add_node:NTP" function, since the graph will not know how to create new unique nodes. All the data structures can be initialized with void |
| attr outgoing_map: FMULTIMAP{NTP,NTP}; .. Included as outgoing_map |
|---|
| **** | Keep both around since it is quite expensive to derive one from the other. |
| attr outgoing_map: FMULTIMAP{NTP,NTP}; .. Included as outgoing_map |
|---|
| **** | Keep both around since it is quite expensive to derive one from the other. |